package training;

import java.util.Arrays;

/**
 * @Author liangzai
 * @Description:
 */
public class J25_6_25_Training {
    //两个有序数组的第 K 小乘积
    public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        //获取数组正负数情况
        int negaCount1 = 0;
        int zeroCount1 = 0;
        for(int num:nums1){
            if (num<0){
                negaCount1++;
            } else if (num==0) {
                zeroCount1++;
            }
        }
        int posiCount1 = len1- negaCount1 - zeroCount1;

        int negaCount2 = 0;
        int zeroCount2 = 0;
        for(int num:nums2){
            if (num<0){
                negaCount2++;
            } else if (num==0) {
                zeroCount2++;
            }
        }
        int posiCount2 = len2- negaCount2 - zeroCount2;

        //乘积正负数数量判断
        long negaStackCount = (long)posiCount1*negaCount2 + (long)posiCount2*negaCount1;
        long zeroStackCount = (long)zeroCount1*len2 + (long)zeroCount2*len1 - (long)zeroCount1*zeroCount2;
        long posiStackCount = (long)posiCount1*posiCount2 + (long)negaCount1*negaCount2;
        int[] negaArr1 = Arrays.copyOfRange(nums1,0,negaCount1);
        int[] posiArr1 = Arrays.copyOfRange(nums1,negaCount1+zeroCount1,len1);
        int[] negaArr2 = Arrays.copyOfRange(nums2,0,negaCount2);
        int[] posiArr2 = Arrays.copyOfRange(nums2,negaCount2+zeroCount2,len2);

        //决定计算范围
        int stackLength;
        long destIndex;
        long[] stackArr;
        if (k > negaStackCount && k < negaStackCount+zeroStackCount+1){
            //0的范围
            return 0L;
        } else if (k <= negaStackCount) {
            //负数范围
            stackArr = new long[(int)negaStackCount];
            long[] multiple1 = multipleArrays(negaArr1,posiArr2);
            long[] multiple2 = multipleArrays(negaArr2,posiArr1);
            combineArrays(stackArr,multiple1,multiple2);
            Arrays.sort(stackArr);
            return stackArr[(int) (k-1)];
        } else {
            //正数范围
            stackArr = new long[(int)posiStackCount];
            long[] multiple1 = multipleArrays(negaArr1,negaArr2);
            long[] multiple2 = multipleArrays(posiArr1,posiArr2);
            combineArrays(stackArr,multiple1,multiple2);
            Arrays.sort(stackArr);
            return stackArr[(int) (k-1-zeroStackCount-negaStackCount)];
        }
    }
    //数组内容相乘
    public long[] multipleArrays(int[] arr1, int[] arr2){
        int currentIndex = 0;
        long[] stackArr = new long[arr1.length*arr2.length];
        for (int num1 : arr1){
            for (int num2 : arr2){
                stackArr[currentIndex] = (long) num1 *num2;
                currentIndex++;
            }
        }
        return stackArr;
    }
    //合并数组
    public void combineArrays(long[] destArr,long[] sourceArr1,long[] sourceArr2){
        int currentIndex = 0;
        for (long num : sourceArr1){destArr[currentIndex] = num;currentIndex++;}
        for (long num : sourceArr2){destArr[currentIndex] = num;currentIndex++;}
    }
}
